For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

0
votes
0answers
11 views

Pippenger's algorithm (or other algorithms) for addition chains with regular binary structure

I'm trying to form an addition chain for a set of numbers that has a semiregular binary structure. For example, consider $x=21651921285435$. It's equal to $\left(2^0 + 2^3 + 2^{12} + 2^{15} + 2^{24} + ...
1
vote
1answer
35 views

3 types of non-infinite coupons in urn with halting, no replacement

An urn has 6 coupons in it. 3 red, 2 blue, 1 green in order to win a prize I must collect a complete set of all the coupons of a particular colour. So all three reds, two blues or just 1 green ...
3
votes
1answer
37 views

Sums and differences of a set of numbers

I am trying to prove that, given a set of $25$ positive numbers, it is always possible to choose a pair of them such that none of the other numbers equals either their sum or their difference. For ...
1
vote
1answer
23 views

Analytical method to compute probability of an event given other event(s)

Suppose event $P(H1)$ denotes the probability of getting exactly one head and $P(T1)$ denotes the probability of getting exactly one tail after tossing two fair coins simultaneously. I am trying ...
0
votes
1answer
35 views

AMC $12A$ Problem (Sequence lengths)

For each positive integer $n$, let $S(n)$ be the number of sequences of length $n$ consisting solely of the letters $A$ and $B$, with no more than three $A$s in a row and no more than three $B$s in ...
0
votes
1answer
47 views

How many ways to pick $4$ numbers (without repetition) from $\{1,2,3,4,5,6,7,8,9\}$ such that the sum of the $4$ numbers is equal to $28$?

How many ways to pick $4$ numbers (without repetition) from $\{1,2,3,4,5,6,7,8,9\}$ such that the sum of the $4$ numbers is equal to $28$? Is there a nice way to approach this problem rather than ...
2
votes
1answer
555 views

Probability of finding specific set of coloured balls within larger set of random-drawn balls

In this question I was helped with calculating the probability of drawing specific set of M coloured balls from a set of N coloured balls. Now I am looking for a solution for an extended problem: ...
0
votes
0answers
11 views

How can i explain the symmetry of the function in a more linguistic manner

To understand the convolution of these functions, please read the following wikipedia page I have the following expression $a = <f'(x),f''(x),\cdots>$ and $b = <g'(x),g''(x),\cdots >$ ...
0
votes
1answer
25 views

Burnside's Lemma and Dominoes

A domino is a thin rectangular piece of wood with two adjacent squares on one side (the other side is black). Each square is either blank or has 1, 2, 3, 4, 5 or 6 dots. Using Burnside's Lemma, show ...
6
votes
3answers
119 views

A closed form for the sum of $(e-(1+1/n)^n)$ over $n$

I have been having some trouble trying to find a closed form for this sum. It seems to converge really slowly
1
vote
2answers
28 views

Interpretation of a Problem involving permutations

[USAMO 1999 submission, Titu Andreescu] Let $n$ be an odd integer greater than $1$. Find the number of permutations $p$ of the set $\{ 1, 2, …, n\}$ for which $$\def\x#1{\lvert p(#1)-#1\rvert} ...
0
votes
1answer
37 views

Stabilizer and Orbit of Groups

Consider $G = <(123),(45)> \subseteq S_5$. What is the stabilizer of $4$, $G_4$, and the orbit of $4$, $G(4)$? Workings: The stabilizer of $x$ is the set of permutations that fix $x$ $G_4 = ...
2
votes
2answers
56 views

Summation over a product of binomial coefficients

Question: I can't figure out why the following equality is true $\sum_\limits{k=a-b-c}^{d} (-1)^k \binom{d}{k}\binom{k+b+c}{a} = (-1)^d \binom{b+c}{a-d} $ How can this be shown? (In the book it just ...
0
votes
1answer
11 views

Reccurence for the numbers of the strip partition

Let's consider a partition of a strip $ 3 \times n$ into $1 \times 2$ rectangles and call $a_{n}$ - the number of such partitions. For instance, $a_{0}=1, a_{1}=0, a_{2}=3, a_{3}=0 \ldots$. How to ...
4
votes
1answer
73 views

Disjoint subsets and Number of 1's in the binary representation

For a subset $S$ of $[n]$, let $\chi(S)$ denote the $n$ bit 'characterisitc vector' of $S$, i.e., $\chi(S)=(a_1, a_2, \ldots, a_n)$ where $a_i=1$ if $i \in S$ and $a_i=0 $ if $i \notin S$. Think of ...
1
vote
0answers
30 views

How many 4 letter words that contain at least 1 vowel can be formed from the word “TOPOLOGIA”?

How many 4 letter words that contain at least 1 vowel can be formed from the word "TOPOLOGIA"? I don't really need the complete solution, more like the reasoning to get to it, I've tried dozens of ...
0
votes
0answers
14 views

Weighted sums with floors

I am interested in the following problem. Suppose $\alpha_1, \cdots, \alpha_n$ are positive real numbers, each at least as large as $1$. Let $D$ be a large positive integer (with respect to the ...
9
votes
1answer
235 views

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color ...
4
votes
1answer
890 views

How many minutes in 1 day?

There are 24*60 minutes in a day (ignoring the imperfections of the natural world, the Earth and Sun). So there are 24*60 valid 24 hour times (excluding seconds) on a digital clock. Each of these ...
2
votes
2answers
38 views

Evaluating the sum $\sum_{k = 0}^n (-1)^{n - k}\binom{n}{k}k$

Let $$a_n=\sum_{k=0}^n (-1)^{n-k}{n \choose k}k$$ I was asked to show that $a_1=1$ and that $\forall n \neq 1, a_n=0$. Showing that $a_1 = 1$ is quite easy, I can manage to show that $a_0 = 0$ but ...
2
votes
1answer
44 views

Unexplicit sum evaluation (Putnam)

For positive integers $n,$ let the numbers $c(n)$ be determined by the rules $c(1)=1,c(2n)=c(n),$ and $c(2n+1)=(-1)^nc(n).$ Find the value of $$S = \sum_{n=1}^{2013}c(n)c(n+2).$$ Let $S_k$ ...
0
votes
0answers
28 views

On exponentials of formal power series

I am having a very hard time trying to understand the following paper by M. Kontsevich (http://arxiv.org/pdf/1109.2469v1.pdf), and since I cannot really find a way out by myself, I here to seek some ...
0
votes
0answers
23 views

Equivalence relation among matrices

Consider the set of $p\times q$ matrices with entries from the set $S=\{1,\dots,s\}$. Say that two such matrices are equivalent if one can be transformed into the other by a series of operations of ...
0
votes
0answers
19 views

Finding Number Of Permutation Reverses

What is the easiest way to count the number of opposite order in permutation. meaning the total of elements in the permutation where $i<j$ and $\sigma_i>\sigma_j$ For example, $3142$, we have ...
0
votes
0answers
12 views

How many undirected 1-regular graphs are possible with set of N nodes? [duplicate]

This can be actually reduced to given set of integers say {1, 2, 3, 4}. How many combinations of pairs possible? For this instance, 3 are possible {(1,2), (3,4)}, {(1,3), (2,4)}, {(1,4), (2,3)}. ...
1
vote
0answers
10 views

Orbital dimension of the action of $S_n$ on 2-subsets

I have a question on a proof in a paper on the orbital dimension of a permutation group. Let $G \le S^\Omega$ be a permutation group. A base for $G$ is a subset $\Sigma \subseteq \Omega$ for which ...
0
votes
0answers
53 views

Probability of picking exactly $k$ number of same color balls from $n$ number of urns with nonuniform ball counts

There are $n$ urns labeled as $1,2,3,\ldots,n$. Each urn contains balls of $m$ different colors labeled as $1,2,3,\ldots,m$. The number of $j_\text{th}$ color ball in the $i_\text{th}$ urn is denoted ...
6
votes
1answer
54 views

Combinatorial proof of an binomial coefficient identity [duplicate]

The identity $$\sum_k \binom{2 k}{k} \binom{2n - 2k}{n - k} = 4^n$$ is found on page 187 of "Concrete Mathematics" by Knuth and Graham. The book does not prove it combinatorially. Is there a proof ...
0
votes
0answers
8 views

Reordering indexed expressions (combinatorics)

To me, it appears always as a little 'magic' when people reorder expressions, indexed by highly complex combinations of permutations and I would like to know in deep and formally what really is going ...
2
votes
1answer
42 views

How many triangles can be formed using 10 points located in each of the sides (but not vertices) of a square?

How many triangles can be formed using 10 points located in each of the sides (but not vertices) of a square? There are a total of $40$ points. Here's how I thought of it: First I have to choose the ...
-1
votes
1answer
23 views

For which $n$ does a bag with $n$ red beads and $5$ blue beads have a probability of $1/6$ that two randomly chosen beads are both red?

A bag contains $n$ red beads and $5$ blue beads. Two beads are taken randomly from the bag. The probability that the two beads are both red is $1/6$. Form an equation involving $n$ and show that it ...
0
votes
2answers
169 views

intuition on multicombinations in combinatorics

I do not understand the formula for multicombinations: Multicombination(n, k) = Combination(n+k-1, k) What is the intuition and maybe even proof behind this formula?
4
votes
1answer
78 views

There are m, n and r points in 3 parallel (different lines). How many triangles can be formed by those points?

There are m, n and r points in 3 parallel (different lines). Supposing that when taking one point from each line they're never aligned. How many triangles can be formed by those points?
1
vote
2answers
25 views

ordering balls in slots

Three balls are to be placed in 8 slots. a. If we distinguish among the balls by naming them $ B_1, B_2, B_3 $, in how many different ways can we do this? I think that this permutation problem, so ...
0
votes
1answer
34 views

Combinatorics Chess Spot Problem

Very tough problem, I must say. NOT CONSIDERING the squares both can go in from one of the black square not considering the squares both can go to. The horse can go to is: $$4 + 4 = 8 \space ...
3
votes
1answer
51 views

Picking Random Elements from Set

Let $S$ be a set consisting of $6$ positiver integers and $8$ negative integers. Choose a 4-element subset of $S$ uniformly at random, and multiply the elements in this subset. Denote the product by ...
3
votes
0answers
15 views

Computer realisation of automorphism group of polyhedron

I have a polyhedron (I am especially interested in the case of Platonic solids) and the graph corresponding to its skeleton. I also have some data associated with this graph (e.g. different ...
0
votes
0answers
25 views

Enumeration of Trees

Find the number of trees of $n$ vertices in which a given vertex is a leaf. I am having difficulty understanding what this question wants me to find. We know the total amount of trees with $n$ ...
3
votes
3answers
86 views

Choosing new teammates

My sister gave me a combinatorical riddle. It doesn't appear to be hard, but I ask you if my thoughts are right, just for certainty. Here it is. Assume you belong to a group of $100$ people, and ...
0
votes
1answer
27 views

on subsets with even intersection

Let $\wp_n$ be the family of all subsets of $[n]$. Let $F_p, F_q\subseteq \wp_n$ s.t. $F_p\neq F_q$. Then, prove that $|\{F_i\subseteq \wp_n\mid | F_i\cap (F_p\bigtriangleup F_q)| \text{ is even}\}| ...
6
votes
0answers
95 views
+100

Check whether a polynomial ideal is prime in the power series ring

I would like to know whether the ideal $I = \langle y^{2}(y^{2}-x^{2}) + w^{7}, y^{2}(y^{4}-x^{4}) + z^{7}\rangle$ is prime in $\mathbb{C}[[x,y,z,w]]$, the ring of formal power series in the ...
2
votes
1answer
17 views

Link between tetrahedral numbers and combinatorics problem?

So I was trying to figure out a combinatorics problem involving the number of unique paths between two coordinates (can't move backwards such as from (1,1) to (0,1)) and I got stuck. I decided to draw ...
7
votes
2answers
46 views

Number of possibility of getting at least a pair of poker cards

The question: randomly drawing a hand (5 cards) from a deck of 52 poker cards, what is the number of possibilities of getting at least one pair in the 5 cards? A pair is two cards within the same ...
0
votes
0answers
32 views

Centralizer of a Group

Consider $G = <(123),(45)> ⊆ S_5$. Find the centralizer of $(123), C_G((123))$ Workings: The centralizer of a group is the set of elements of $G$ that commute with each element of $S$. So I ...
2
votes
2answers
33 views

Need help with a hard combinatorics problem

I can't solve the following combinatorics problem from the european kangaroo competition. Four cars enter a roundabout at the same time, each one from a different direction, as shown in the diagram. ...
4
votes
1answer
28 views

Is there a reference for the following generating function identities?

For the Motzkin and Schröder numbers respectively, we have the following identities: $$ Mk(z) = \sum_{n=1}^{\infty} \Bigg{(} -\frac{1}{2} \sum_{a=0}^{n+2} (-3)^{k} \binom{\frac{1}{2}}{a} \binom{ ...
1
vote
1answer
79 views

Why General Leibniz rule and Newton's Binomial are so similar?

The binomial expansion: $$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$ The General Leibniz rule (used as a generalization of the product rule for derivatives): $$(fg)^{(n)} = ...
3
votes
2answers
103 views

Ball and urn method (counting problems)

How many ordered triples $(a, b, c)$ of positive integers exist with the property that $abc = 500$? Since, $500 = 2^2 5^3$ I believe this can be solved using Ball and Urn let $a = ...
1
vote
1answer
28 views

Count the number of one pair hands in a standard deck

In an attempt to answer this question, I tried the following solution: Let $A$ denote the number of one-pair hands Let $B$ denote the number of two-pair hands Let $C$ denote the number of ...
-1
votes
1answer
60 views

Result of a $2D$ random walk after $n$ steps

One of my friends(who is around $8$ years bigger) gave me the following question:- A man is initially at the origin and can move in a line parallel to the X and Y-axis only. Given that the man takes ...