This tag is for basic 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 (5)

3
votes
1answer
102 views

Average result of game

I'm trying to find the average result for a game where you have 12 items (containing a score), you can pick up to five of them, one of them is a multiplier, that when selected multiplies your result ...
1
vote
1answer
171 views

Proof for Matroids: Independence Oracle is polynomial equivalent to Basis Super-Set Oracle

Task: Given an Independence Oracle and a Basis Super-Set Oracle I want to proove, that they are polynomial equivalent for Matroids. First I tried to update my knowledge about the topic. Let ...
7
votes
2answers
599 views

Stirling Numbers and inverse matrices

Let $s(m,n)$ be the Stirling Numbers of the first kind, $S(m,n)$ be the Stirling Numbers of the second kind. The matrices $$\mathcal{S}_N := (S(m,n))_{N \geq m,n \geq 0} \text { and } \mathcal{s}_N ...
5
votes
1answer
722 views

(Extended) Hall's Marriage Theorem from Dilworth's Theorem

This question comes from Exercises III.4.5 and III.4.6 of Bourbaki's Set Theory. They are about using Dilworth's Theorem to prove Hall's Marriage Theorem (did it) and a mild extension of it (can't do ...
3
votes
2answers
835 views

The number of bit strings with only two occurrences of 01

How many bit strings of length $n$, where $n \geq 4$, contain exactly two occurrences of $01$?
4
votes
4answers
2k views

To prove there exist two relatively prime numbers in a finite set

Prove that in any set of $n+1$ positive numbers not exceeding $2n$ there must be two that are relatively prime.
1
vote
1answer
45 views

Distribution of number of special elements chosen: m choices of n items with k special items

Suppose I a set with $n$ items, $k$ of which have a certain property($k\leq n$), and I choose $m$ items randomly from that set($m\leq n$), what is the distribution of the number of chosen items having ...
4
votes
3answers
405 views

What's the chance of an explicit series of integers in a limited random distribution?

Say I collect 40 perfectly random integers between 1 and 400. What's the chance that any integer is repeated consecutively six times in such a random draw? What I'm looking for is the chance of ...
2
votes
1answer
143 views

question about counting recursively

The the question is from the following problem: Acceptable input for a certain pocket calculator is a finite sequence of characters each of which is either a digit or a sign. The first character ...
2
votes
3answers
261 views

Squares on a checkerboard

How many squares of all sizes arise using an $n$-by-$n$ checkerboard? How many triangles of all sizes arise using a triangular grid with sides of length $n$ ?
2
votes
2answers
121 views

Number of variations from specific set

With a given set $A=\{{0,...,N\}}$ we can choose only $H$ numbers from it (we can pick same number many times), And put them in a row. The sum of those numbers has to be some given $X$. The first ...
1
vote
1answer
84 views

Looking for a combinatorical explanation

Let $X_n$ be the set of all word of the length $2 n$ over the alphabet $\{A,B\}$ which contain as many A's as B's. The amount of elements of $X_n$ is $\displaystyle \binom{2n}{n}$, but why? I ...
1
vote
3answers
94 views

Counting words with three letters

Let $X_n$ be the set of all word of the length $3 n$ over the alphabet $\{A,B,C\}$ which contain each of the three letters n times. The amount of elements of $X_n$ is $\frac{(3n)!}{(n!)^3}$, but why? ...
11
votes
4answers
817 views

Combinatorial proof that binomial coefficients are given by alternating sums of squares?

A student recently asked whether there was a combinatorial proof of the following identity: $\begin{equation*} \sum^n_{k=1}(-1)^{n-k}k^2 = {n+1 \choose 2}. \end{equation*}$ I was in a rush and ...
2
votes
3answers
79 views

Number of digits in a series of numbers

I have a list of the numbers from 1 to 1000. How can I find the number of 0's, 1's, 2's, and 9's that are used? The answers are 192, 301, 300, 300 respectively, but I'm interested in the process ...
0
votes
1answer
127 views

subgraphs of $K_n$ upto isomorphism

I am trying to make a list of all subgraphs up to isomorphism of $K_n$. (Not of all the $2^{\tbinom{n}{2}}$ subgraphs; only up to isomorphism.) I have two questions: Is there a formula which will ...
17
votes
4answers
648 views

Is there a way to prove $\int {x^n e^x dx} = e^x \sum_{k = 0}^n {( - 1)^k \frac{{n!}}{{(n-k)!}}x^{n-k} } + C$ combinatorially?

In How to integrate $\int x^n e^x dx$?, it is shown that $$\int {x^n e^x dx} = e^x \sum_{k = 0}^n ( - 1)^k \frac{n!}{(n-k)!}x^{n-k} + C.$$ Since $\frac{n!}{(n-k)!}$ is $P(n,k)$, the number of ...
1
vote
3answers
1k views

Permutation/Combinations in bit Strings

I have a bit string with 10 letters, which can be {a, b, c}. How many bit strings can be made that have exactly 3 a's, or exactly 4 b's? I thought that it would be C(7,2) + C(6,2), but that's wrong ...
4
votes
1answer
268 views

Partial sum of ${A \choose i} {B\choose n-i}$, when $B=-1$?

It's easy to see that $$ \sum_i {A\choose i} {B\choose n-i} = {A+B\choose n} $$ since when we choose $n$ things out of $A+B$, some ($i$ of them) are in the $A$ and the rest are in the $B$. Is there ...
1
vote
2answers
671 views

Finding Integers using Counting Rules

I'm studying, and got this problem in the book, How many positive integers between 50 and 100 are divisible by 7, and what are they? The same for number divisible by both 7 and 11. I'm ...
3
votes
2answers
103 views

Digit in the ten's place of an expression

What is the digit in the ten's place of $23^{41}* 25^{40}$ ? How do you calculate this? The usual method for this kind of problem is using the Binomial theorem, but I couldn't solve it.
0
votes
1answer
489 views

Probability of at least one event from a subset happening when choosing 2 out of 4 possible events

We have a complete set of events $\{A,B,C,D\}$. $p(A)=0.2$ $p(B)=0.3$ $p(C)=0.4$ $p(D)=0.1$ Two events happen in succession, where each event cannot occur twice. (i.e. when one happens the others' ...
0
votes
1answer
58 views

Describing fans from hyperplanes

If $H_1, ..., H_n$ are hyperplanes in $\mathbb{R}^m$ such that the complement of the union $\cup_i H_i$ is the interior of a complete polyhedral fan, then how does one determine ray generators for ...
7
votes
5answers
1k views

Proof that cube has 24 rotational symmetries

I was doing a combinatorics problem which states this definition of symmetry: for a subset $S$ of $\mathbb{R}^3$ a symmetry is "rigid motion" $f:\mathbb{R^3}\rightarrow \mathbb{R^3}$ such that any ...
0
votes
1answer
127 views

Proving a Recursive Relation

I’m studying for an exam, and have this problem as one of my review questions: I have $p(n)$, which represents the amount of partitions from a set $A$ that has $n$ elements. I know that if $R$ is an ...
5
votes
1answer
178 views

Asymptotic formula for $k$-partitions of a number

Asymptotic formula for all the partitions of a number is given by $$p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$$ Only fraction of those will be $k$-partitions. What is asymptotic ...
6
votes
5answers
657 views

Permutations Problem

i'm having a bit of an issue with solving a permutations problem Find the number of ways in which 4 boys and 4 girls can be seated in a row of 8 seats if they sit alternately. Okay, well.. Simple ...
2
votes
4answers
159 views

Combinatorics Question

I have letters 'a', 'b', and 'c'. What's the formula to get all possible combinations? Like for 'a' and 'b' would be: 'a', 'b', 'aa','ab', 'ba' and 'bb'. And what is this called, Permutations?
5
votes
3answers
361 views

How many ways can 70 planes be allocated into 4 runways?

I'm doing some preparations for an upcoming exam, and a little confused about this problem: "In an airport, 70 flight landings per hour are allocated among 4 runways. Any flight can land on any ...
2
votes
1answer
562 views

Problem with proving Hall marriage theorem

I have a question about the proof of this theorem. If modeled with graphs, theorem would go like this: Marriage problem: Let $V_1$ and $V_2$ be the disjunct set of vertices in a bipartite graph, ...
3
votes
1answer
81 views

Combination of 24 picture cards

Twenty-four picture cards can be combined $1\,686\,553\,615\,927\,922\,354\,187\,744$ times. This means that you can get a complete landscape even with the quadrillionth variant. The result can be ...
8
votes
1answer
81 views

about a subset of the multidimensional cube

Let $[0,1]^{n+2}$ be the ($n+2)$-dimensional unit cube. Consider the set $A\subset[0,1]^{n+2}$ consisting of all points $(x_{1},...,x_{n+2})$ such that $x_{i}=0$, $x_{j}=1$ for some ...
3
votes
1answer
231 views

Counting/Probability problem involving runs of a given length

Suppose we have a row of $c\,W$ elements. We select half of them, $\displaystyle \frac{c\,W}{2}$. What is the probability that we have at least one run of at least $W$ selected elements, in terms of ...
6
votes
1answer
197 views

Does there exist a Latin square of order 16 that admits a specific automorphism?

One of the perks of my research topic (Latin squares) is that it's somewhat possible to explain what I do to those with a fairly minimal mathematics background. I'll pose a typical question that ...
9
votes
3answers
534 views

Largest Part of a Random Weak Composition

Suppose we have a weak composition of the integer n into k parts. (A weak compositions is essentially a partition in which order matters and 0 is allowed) My question is, what is the expected value ...
9
votes
4answers
224 views

Bounding ${(2d-1)n-1\choose n-1}$

Claim: ${3n-1\choose n-1}\le 6.25^n$. Why? Can the proof be extended to obtain a bound on ${(2d-1)n-1\choose n-1}$, with the bound being $f(d)^n$ for some function $f$? (These numbers ...
1
vote
0answers
312 views

Solution to rarity-generalized coupon-collector's problem? [duplicate]

Possible Duplicate: A Question About Dice I was reading " Expected time to roll all 1 through 6 on a die " and it got me thinking... There are various ways to generalize the ...
1
vote
1answer
285 views

Two generating functions involving binomial coefficients

Are any of you familiar with the closed form solutions for $\sum_{k=0}^{n} k C(n,k) x^k$ and $\sum_{k=0}^{n} k^2 C(n,k) x^k$ where $0 < x < 1$? Thanks!
8
votes
4answers
362 views

Unique Groups for Game Tournament

I am trying to put together a Munchkin game tournament where I am assuming I will have 16 people coming to my tournament. As part of that, I want to have as many games as possible where people are not ...
0
votes
1answer
213 views

Meaning of the question

There is a question that goes like this : The supreme court has given a 6 to 3 decisions upholding a lower court; the number of ways it can give a majority decision reversing the lower court is : ...
2
votes
1answer
77 views

Distributions of input in knapsack problem & related

Let's say that I magicked up some algorithm that would solve subset sum problem in polynomial time, if and only if the input set N was roughly uniformly distributed. Would that count as a polynomial ...
2
votes
1answer
184 views

Upper bound a binomial-like summation

I am attempting to prove a non-trivial upper bound on the following expression. Let $0 < r \leq 1$, and let $p$ be a positive integer. My summation is the following: $$\sum_{k=0}^\left\lfloor ...
4
votes
1answer
245 views

A generating function for walks on a rooted infinite regular tree

Consider $T_d$ the $d$-regular infinite tree rooted at some vertex $v_0$. I'd like to count all the closed walks on the tree which start at the root and order them by their length. So I'm looking for ...
5
votes
3answers
646 views

Probability of picking all elements in a set

I was studying the birthday paradox and got curious about a related, but slightly different problem. Lets say I have a set S, that has n unique elements. If I randomly pick k elements from the set ...
2
votes
1answer
97 views

$1$D bidirectional random walk question

In a $1$D random walk on x axis a particle can turn left with probability $\frac{3}{4}$ and right with probability $\frac{1}{4}$. What is the probability that $|x|\leq 1 $ for $1\leq ...
1
vote
1answer
148 views

Knapsack problem and sub-problems- clarification

I'm reading up about the Knapsack problem on Wiki and it's associated problem, the subset sum problem. However, the language is a little vague, so I'd like to clarify about what exactly is going on ...
4
votes
3answers
396 views

Evaluate $\displaystyle \sum_{k=1}^n \binom{2k}{2}$ combinatorially

How to evaluate the expression $$\displaystyle \sum_{k=1}^n \binom{2k}{2}$$ using a combinatorial argument? Sorry I have little clue so cannot provide any working for it. Not homework. Related to ...
1
vote
1answer
342 views

Combinations of a specific size to sum to a specific N

I'm looking to find a way, for any N, to generate all the combinations (definitely not permutations) of size N, which sum to N-1, involving (including repetition) 0 to N-1, where N >= 3. For example, ...
1
vote
1answer
109 views

are there useful bounds on the “gamma” coeficients (generalization of multinomial coefficients)?

Let $a_1,\ldots,a_n$ be a set of $n$ positive numbers. Are there known lower and upper bounds on: $\displaystyle\frac{\prod_{i} \Gamma(a_i)}{\Gamma(\sum_i a_i)}$ where $\Gamma$ is the Gamma ...
2
votes
0answers
204 views

Asymptotic bounds for a sum

I have this sum, which probably doesn't exist in closed form. $$\displaystyle ...